#pragma once
#include <cassert>
#include <cstdint>
#include <cstring>
#include <algorithm>
#include "MBitSet.h"


template <typename T=int> 
class RandSet{    
public:
    using TIndex = uint16_t;
    int sz;
    int cap;
    T *members;
    TIndex *pos; 
    MBitSet32 *flag;
    
public:
    static constexpr int CAP_LIMIT = 1<<16;

    //default constructor        
    RandSet():sz(0),cap(0),members(nullptr),flag(nullptr),pos(nullptr){}

    RandSet(int _maxvalue):cap(_maxvalue),sz(0){       
        assert(_maxvalue < CAP_LIMIT) ;
        members = new T[_maxvalue];
        pos = new TIndex[_maxvalue];
        flag = new MBitSet32(_maxvalue);
    }

    
    RandSet(const RandSet &_set){// copy constructor
        cap = _set.cap;
        sz = _set.sz;
        
        members = new T[cap];
        memcpy(members, _set.members, sizeof(T) * sz);

        pos = new TIndex[cap];
        memcpy(pos, _set.pos, sizeof(TIndex) * cap);

        flag = new MBitSet32(*(_set.flag));        
        
    }
    RandSet& operator=(const RandSet &_set) = delete;
    //deep copy
     /*
    RandSet& clone(const RandSet &_set){
                cap = _set.cap;
        sz = _set.sz;
        
        members = new T[cap];
        memcpy(members, _set.members, sizeof(T) * sz);

        pos = new TIndex[cap];
        memcpy(pos, _set.pos, sizeof(TIndex) * sz);

        flag = new MBitSet32(*(_set.flag)); // copy constructor;
    }
   
    RandSet& operator=(const RandSet &_set){        
        cap = _set.cap;
        sz = _set.sz;

        if (members!= nullptr) delete[] members;
        members = new T[cap];
        memcpy(members, _set.members, sizeof(T) * sz);

        if (pos != nullptr) delete[] pos;
        pos = new TIndex[cap];
        memcpy(pos, _set.pos, sizeof(TIndex)*sz);

        if (flag != nullptr) delete flag;
        flag = new MBitSet32(*(_set.flag));
    }*/
    

    ~RandSet(){
        delete[] members;
        delete[] pos;
        delete flag;        
    }

    

    inline bool contains(const T& v){
        assert(v < cap);        
        return flag->test(v);
    }

    bool add(const T& v){
        if (!contains(v)){
            pos[v] = sz; 
            members[sz++]=v;
            flag->set(v); 
            return true;           
        }
        return false;
    }

    bool remove(const T& v){
        assert(sz > 0);
        if (contains(v)){
            TIndex idx = pos[v];            
            pos[members[sz-1]] = idx;
            std::swap(members[idx], members[--sz]);                        
            //sz--;
            flag->set(v);
            return true;
        }
        return false;
    }
     
    inline int size(){
        return sz;
    }


    RandSet& operator+(const T& v){
        add(v);
        return *this;
    }

    
    T& operator[](const TIndex i){
        assert(i < sz);
        return members[i];
    }

    void clear(){
        flag->clear();
        sz = 0;                
    }

    template<typename Fnc>
    void for_each(const Fnc &f){        
        for (TIndex i = 0; i < sz; i++){
            f(members[i]);
        }
    }
};

